#!/usr/bin/python3
#!/usr/bin/python3
while 1:
    try:
        t = input()
        t = int(t)
        list_ret = []
        while t > 0:
                n, m = input().split()
                i = 1
                j = 0
                if n != "" and m != "":
                    n = int(n)
                    m = int(m)
                    while 1:
                        i = i+m
                        if i<=n :
                            j = j + 1
                        elif i%n!=1:
                            i = i%n
                            j = j + 1
                        else :
                            j = j + 1
                            list_ret.append(j)
                            break
                    t = t - 1
                else : break
        for i,ret in enumerate(list_ret,0):
            print("Case #%s: %s" % (i + 1,ret))
    except ValueError:
        pass
    except MemoryError:
        break